파이썬 리스트는 하위 계층에서 느슨한 연결 리스트가 아니라 고도로 조직화된 ArrayList입니다. 핵심 진실은 메모리에 연속된 주소 공간을 차지한다는 것입니다. 여기에는 객체 자체가 저장되는 것이 아니라 객체를 가리키는 참조입니다(또는 C 언어 수준에서는 포인터). 이러한 설계는 다양한 데이터 유형을 통합적으로 관리할 수 있게 해줍니다. 색상 값(RGB) 튜플이나 복잡한 암호 키(Key)와 같은 경우에도 고정된 크기의 포인터만 차지하면 됩니다.

주소 접근 수학과 성능 균형

• $O(1)$ 랜덤 접근공식 $\text{요소 주소} = \text{시작 주소} + \text{인덱스} \times \text{크기}$를 통해 CPU는 즉시 위치를 확인할 수 있습니다.
• 균등 분석 (Amortized Analysis)과잉 할당 전략을 활용하여, 단일 삽입 시 $O(n)$일 수 있지만, $\text{총 비용} = n + \sum_{j=0}^{\lg n} 2^j = 3n$로 균등 $O(1)$의 추가 성능을 보장합니다.
• 삽입 제한Figure 8-2처럼 임의의 위치에 `insert`하려면 이후 모든 포인터를 이동해야 하며, 시간 복잡도는 $O(n)$입니다.